{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Distinct Substrings in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #string #suffix-array #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #字符串 #后缀数组 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countDistinct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的不同子字符串个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code>，返回 <code>s</code> 的不同子字符串的个数。</p>\n",
    "\n",
    "<p>字符串的 <strong>子字符串 </strong>是由原字符串删除开头若干个字符（可能是 0 个）并删除结尾若干个字符（可能是 0 个）形成的字符串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aabbaba\"\n",
    "<strong>输出：</strong>21\n",
    "<strong>解释：</strong>不同子字符串的集合是 [\"a\",\"b\",\"aa\",\"bb\",\"ab\",\"ba\",\"aab\",\"abb\",\"bab\",\"bba\",\"aba\",\"aabb\",\"abba\",\"bbab\",\"baba\",\"aabba\",\"abbab\",\"bbaba\",\"aabbab\",\"abbaba\",\"aabbaba\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcdefg\"\n",
    "<strong>输出：</strong>28\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 500</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成。</li>\n",
    "</ul>\n",
    "\n",
    "<p><b>进阶：</b>你可以以 <code>O(n)</code> 时间复杂度解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-distinct-substrings-in-a-string](https://leetcode.cn/problems/number-of-distinct-substrings-in-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-distinct-substrings-in-a-string](https://leetcode.cn/problems/number-of-distinct-substrings-in-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabbaba\"', '\"abcdefg\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2,len(s) - k + 1,10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        p=len(s)-k+1\n",
    "        return 2**p%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        return 2**(n-k+1)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 数学\n",
    "    # 考虑s中长度为k的子串有len(s) - k + 1个,每个子串有翻转与不翻转两个状态\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2, len(s) - k + 1, 10 ** 9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2, len(s) - k + 1, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "# from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "def pow_mod(a, k, p):\n",
    "    ans = 1\n",
    "    pow_val = a % p # a的2^0次方，数值就是a\n",
    "    while k != 0:\n",
    "        if k & 1 != 0:\n",
    "            ans = (ans * pow_val) % p\n",
    "        pow_val = (pow_val ** 2) % p\n",
    "        k >>= 1\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        x = len(s)-k+1\n",
    "        return pow_mod(2, x, MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        # 脑筋急转弯\n",
    "        # 由于每一段区间只有翻转和不翻转\n",
    "        # 可以翻转的长度为 (n - k) + 1\n",
    "        # 所以可能性为 2**p\n",
    "        return pow(2, (len(s)-k+1), int(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2,len(s)-k+1,1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2,len(s) - k + 1,10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2, len(s) - k + 1, 10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        if len(s) ==1:\n",
    "            return 1\n",
    "        ansSet = set()\n",
    "        for size in range(1,len(s)):\n",
    "            for left in range(len(s)+1):\n",
    "                t = s[left:left+size]\n",
    "                ansSet.add(t)\n",
    "        return len(ansSet)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# if len(s) == 1:\n",
    "#             return 1\n",
    "#         ansSet = set()\n",
    "#         for size in range(1,len(s)):\n",
    "#             for left in range(len(s)+1):\n",
    "#                 t = s[left:left+size]\n",
    "#                 ansSet.add(t)\n",
    "#         ans = []\n",
    "#         for e in ansSet:\n",
    "#             ans.append(e)\n",
    "#         return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        return len(set(s[i:j+1] for i in range(len(s)) for j in range(i, len(s))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        subSet = set()\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i, len(s)):\n",
    "                subSet.add(s[i:j+1])\n",
    "        return len(subSet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        ans = set()\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1):\n",
    "                if s[j:i+1] not in ans: ans.add(s[j:i+1])\n",
    "                else:   break\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        distinct_substrings = set()  # 创建一个空集合来保存不同的子字符串\n",
    "        n = len(s)\n",
    "        \n",
    "        # 生成所有可能的子字符串并添加到集合中\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n+1):\n",
    "                distinct_substrings.add(s[i:j])\n",
    "                \n",
    "        return len(distinct_substrings)  # 返回集合的大小，即不同子字符串的数量\n",
    "\n",
    "# 示例\n",
    "sol = Solution()\n",
    "print(sol.countDistinct(\"abcabc\"))  # 输出应为 10 (\"a\", \"ab\", \"abc\", \"b\", \"bc\", \"c\", \"ca\", \"cab\", \"a\", \"b\")\n",
    "print(sol.countDistinct(\"aaa\"))  # 输出应为 3 (\"a\", \"aa\", \"aaa\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        ss = set()\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                ss.add(s[i:j+1])\n",
    "        return len(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class RollingHash:\n",
    "    def __init__(self, s, base1=31, base2=71):\n",
    "        n = len(s)  # s 要处理的字符串\n",
    "        self.MOD = 10 ** 18 + 7 # 是必要的，否则计算速度超级慢\n",
    "        # encoder：获取字母在字母表中的顺序:\n",
    "        ecd = {chr(i + ord('a')): i for i in range(26)}\n",
    "        hvs1, hvs2 = [0] * (n + 1), [0] * (n + 1)\n",
    "        pow1, pow2 = [1] * (n + 1), [1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            hvs1[i + 1] = (hvs1[i] * base1 + ecd[s[i]]) % self.MOD\n",
    "            hvs2[i + 1] = (hvs2[i] * base2 + ecd[s[i]]) % self.MOD\n",
    "            pow1[i + 1] = (pow1[i] * base1) % self.MOD\n",
    "            pow2[i + 1] = (pow2[i] * base2) % self.MOD\n",
    "        self.hvs1, self.hvs2 = hvs1, hvs2\n",
    "        self.pow1, self.pow2 = pow1, pow2\n",
    "\n",
    "    # 获取子串s[start:end)哈希值，元组形式返回:\n",
    "    def get_hash(self, start, end):\n",
    "        hash_1 = (self.hvs1[end] - self.hvs1[start] * self.pow1[end - start]) % self.MOD\n",
    "        hash_2 = (self.hvs2[end] - self.hvs2[start] * self.pow2[end - start]) % self.MOD\n",
    "        return (hash_1, hash_2)\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = set()\n",
    "        for l in range(n):\n",
    "            for r in range(l+1, n+1):\n",
    "                ans.add(s[l:r])\n",
    "        return len(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self) -> None:\n",
    "        self.next = {}\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def add(self, word):\n",
    "        count = 0\n",
    "        curr = self.root\n",
    "        for w in word:\n",
    "            if w not in curr.next:\n",
    "                curr.next[w] = TrieNode()\n",
    "                count += 1\n",
    "            curr = curr.next[w]\n",
    "        return count\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        t = Trie()\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            res += t.add(s[i:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.next = {}\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def add(self, word):\n",
    "        count = 0\n",
    "        curr = self.root\n",
    "        for w in word:\n",
    "            if w not in curr.next:\n",
    "                curr.next[w] = TrieNode()\n",
    "                count += 1\n",
    "            curr = curr.next[w]\n",
    "        return count\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, s: str) -> int:\n",
    "        t = Trie()\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            res += t.add(s[i:])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
